package 代码随想录_动态规划.背包_01;

/**
 * @author zx
 * @create 2022-05-30 17:40
 */
public class 一和零_474 {
    /**
     * @return 二维的背包问题,没太理解相当于cv
     * 具体理解看代码随想录
     */
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
        int[][] dp = new int[m + 1][n + 1];
        for(int k = 0;k < strs.length;k++){
            int oneNum = 0,zeroNum = 0;
            for(int h = 0;h < strs[k].length();h++){
                if(strs[k].charAt(h) == '0'){
                    zeroNum++;
                }else{
                    oneNum++;
                }
            }
            //因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
            //遍历背包容量的两层for循环先后循序,都是物品重量的一个维度，先遍历那个都行！
            for(int i = m;i >= zeroNum;i--){
                for(int j = n;j >= oneNum;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
